package org.nvm.core;

public class QuickSortSet {

	private Cell head;
	
	private Cell tail;
	
	private int size;
	
	public QuickSortSet() {
		this.size = 0;
	}
	
	boolean addLexeme(Lexeme lexeme) {
		Cell cell = new Cell(lexeme);
		if(this.size == 0) {
			this.head = cell;
			this.tail = cell;
			this.size ++;
			return true;
		}
		
		int compareToTail = this.tail.compareTo(cell);
		if(compareToTail == 0) {
			return false;
		}
		if(compareToTail < 0) {//cell 排到尾部
			cell.prev = this.tail;
			this.tail.next = cell;
			this.tail = cell;
			this.size ++;
			return true;
		}
		
		if(this.head.compareTo(cell) > 0) {//cell放入到头部
			cell.next = this.head;
			this.head.prev = cell;
			
			this.head = cell;
			this.size ++;
			return true;
		}
		
		Cell index = this.tail;
		
		while((index != null) && index.compareTo(cell) > 0) {
			index = index.prev;
		}
		if(index.compareTo(cell) == 0) {
			return false;
		}
		
		//cell插入到index位置后面的位置
		index.next.prev = cell;
		cell.next = index.next;
		cell.prev = index;
		index.next = cell;
		this.size ++;
		
		return true;
	}
	
	Lexeme getHead() {
		if(this.head != null) {
			return this.head.lexeme;
		}
		return null;
	}
	Lexeme shiftHead() {
		if(this.size <= 0) {
			return null;
		}

		if(this.size == 1) {
			Lexeme lexeme = this.head.lexeme;
			this.head = null;
			this.tail = null;
			this.size --;
			
			return lexeme;
		} else {
			Lexeme lexeme = this.head.lexeme;
			this.head = this.head.next;
			this.size --;
			
			return lexeme;
		}
	}
	Lexeme getTail() {
		if(this.tail != null) {
			return this.tail.lexeme;
		}
		return null;
	}
	Lexeme shiftTail() {
		if(this.size <= 0) {
			return null;
		}

		if(this.size == 1) {
			Lexeme lexeme = this.tail.lexeme;
			this.head = null;
			this.tail = null;
			this.size --;
			
			return lexeme;
		} else {
			Lexeme lexeme = this.tail.lexeme;
			this.tail = this.tail.prev;
			this.size --;
			
			return lexeme;
		}
	}
	
	public int size() {
		return this.size;
	}
	public boolean isEmpty() {
		return this.size <= 0;
	}
	Cell getHeadCell() {
		return this.head;
	}
	
	class Cell implements Comparable<Cell> {
		private Cell prev;
		private Cell next;
		private Lexeme lexeme;
		
		public Cell(Lexeme lexeme) {
			super();
			if(lexeme == null) {
				throw new IllegalArgumentException("lexeme is null");
			}
			this.lexeme = lexeme;
		}

		@Override
		public int compareTo(Cell o) {
			return this.lexeme.compareTo(o.lexeme);
		}

		public Cell getPrev() {
			return prev;
		}
		public Cell getNext() {
			return next;
		}
		public Lexeme getLexeme() {
			return lexeme;
		}
		
	}
}
